home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1996 July: Mac OS SDK / Dev.CD Jul 96 SDK / Dev.CD Jul 96 SDK1.toast / Development Kits (Disc 1) / OpenDoc / OpenDoc Development / Debugging Support / OpenDoc Source Code / Utilities / Node.cpp < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-22  |  13.4 KB  |  594 lines  |  [TEXT/MPS ]
  1. /*
  2.     File:        Node.cpp
  3.  
  4.     Contains:    Implementation of Node class
  5.  
  6.     Owned by:    Richard Rodseth
  7.  
  8.     Copyright:    © 1993 - 1995 by Apple Computer, Inc., all rights reserved.
  9.  
  10.     To Do:
  11.         Optimization: Many methods could be inlined for speed & code size improvements.
  12. */
  13.  
  14. #ifndef _NODE_
  15. #include "Node.h"
  16. #endif
  17.  
  18. #ifndef _EXCEPT_
  19. #include "Except.h"
  20. #endif
  21.  
  22. #ifndef _ODDEBUG_
  23. #include "ODDebug.h"
  24. #endif
  25.  
  26.  
  27. #pragma segment ODNode
  28.  
  29. //======================================================================================
  30. // Class Node
  31. //======================================================================================
  32.  
  33. //------------------------------------------------------------------------------
  34. // Node::Node
  35. //
  36. // Description
  37. //------------------------------------------------------------------------------
  38.  
  39. Node::Node() 
  40. {
  41.     fParent = kODNULL; 
  42. }
  43.  
  44. //------------------------------------------------------------------------------
  45. // Node::~Node
  46. //
  47. // Description
  48. //------------------------------------------------------------------------------
  49.  
  50. Node::~Node() 
  51. {
  52. }
  53.  
  54. //------------------------------------------------------------------------------
  55. // Node::Node
  56. //
  57. // Description
  58. //------------------------------------------------------------------------------
  59.  
  60. ODULong Node::Size() 
  61. {
  62.     ODULong size = 0;
  63.     
  64.     Node* node = this->FirstTopDown();
  65.     while (node)
  66.     {
  67.         size++;
  68.         node = node->NextTopDown(kODFrontToBack);
  69.     }
  70.     return size;
  71. }
  72.  
  73. //------------------------------------------------------------------------------
  74. // Node::Node
  75. //
  76. // Description
  77. //------------------------------------------------------------------------------
  78.  
  79. Node* Node::GetParent()
  80. {
  81.     return fParent;
  82. }
  83.  
  84. //------------------------------------------------------------------------------
  85. // Node::Node
  86. //
  87. // Description
  88. //------------------------------------------------------------------------------
  89.  
  90. Node* Node::GetFirstChild()
  91. {
  92.     return (Node*) this->First();
  93. }
  94.  
  95. //------------------------------------------------------------------------------
  96. // Node::Node
  97. //
  98. // Description
  99. //------------------------------------------------------------------------------
  100.  
  101. Node* Node::GetLastChild()
  102. {
  103.     return (Node*) this->Last();
  104. }
  105.  
  106. //------------------------------------------------------------------------------
  107. // Node::Node
  108. //
  109. // Description
  110. //------------------------------------------------------------------------------
  111.  
  112. Node* Node::GetNextSibling()
  113. {
  114.     Node* parent = this->GetParent();
  115.     return parent ? parent->GetChildAfter(this) : kODNULL;
  116. }
  117.  
  118. //------------------------------------------------------------------------------
  119. // Node::Node
  120. //
  121. // Description
  122. //------------------------------------------------------------------------------
  123.  
  124. Node* Node::GetChildAfter(Node* node)
  125. {
  126.     return (Node*) this->After(*node);
  127. }
  128.  
  129. //------------------------------------------------------------------------------
  130. // Node::Node
  131. //
  132. // Description
  133. //------------------------------------------------------------------------------
  134.  
  135. Node* Node::GetChildBefore(Node* node)
  136. {
  137.     return (Node*) this->Before(*node);
  138. }
  139.  
  140. //------------------------------------------------------------------------------
  141. // Node::Node
  142. //
  143. // Description
  144. //------------------------------------------------------------------------------
  145.  
  146. Node* Node::GetPreviousSibling()
  147. {
  148.     Node* parent = this->GetParent();
  149.     return parent ? parent->GetChildBefore(this) : kODNULL;
  150. }
  151.  
  152. //------------------------------------------------------------------------------
  153. // Node::Node
  154. //
  155. // Description
  156. //------------------------------------------------------------------------------
  157.  
  158. void Node::SetParent(Node* parent)
  159. {
  160.     fParent = parent;
  161. }
  162.  
  163. //------------------------------------------------------------------------------
  164. // Node::Node
  165. //
  166. // Description
  167. //------------------------------------------------------------------------------
  168.  
  169. void Node::AddChildFirst(Node* node)
  170. {
  171.     node->SetParent(this);
  172.     this->AddFirst(node);
  173. }
  174.  
  175. //------------------------------------------------------------------------------
  176. // Node::Node
  177. //
  178. // Description
  179. //------------------------------------------------------------------------------
  180.  
  181. void Node::AddChildLast(Node* node)
  182. {
  183.     node->SetParent(this);
  184.     this->AddLast(node);
  185. }
  186.  
  187. //------------------------------------------------------------------------------
  188. // Node::Node
  189. //
  190. // Description
  191. //------------------------------------------------------------------------------
  192.  
  193. void Node::AddChildBefore(Node& existing, Node* node)
  194. {
  195.     node->SetParent(this);
  196.     this->LinkedList::AddBefore(existing, node);
  197. }
  198.  
  199. //------------------------------------------------------------------------------
  200. // Node::Node
  201. //
  202. // Description
  203. //------------------------------------------------------------------------------
  204.  
  205. void Node::AddChildAfter(Node& existing, Node* node)
  206. {
  207.     node->SetParent(this);
  208.     this->LinkedList::AddAfter(existing, node);
  209. }
  210.  
  211. //------------------------------------------------------------------------------
  212. // Node::Node
  213. //
  214. // Description
  215. //------------------------------------------------------------------------------
  216.  
  217. void Node::RemoveChild(Node& child)
  218. {
  219.     this->LinkedList::Remove(child);
  220. }
  221.  
  222. //------------------------------------------------------------------------------
  223. // Node::Node
  224. //
  225. // Description
  226. //------------------------------------------------------------------------------
  227.  
  228. Node* Node::FirstTopDown()
  229. {
  230.     return this;
  231. }
  232.  
  233. //------------------------------------------------------------------------------
  234. // Node::Node
  235. //
  236. // Description
  237. //------------------------------------------------------------------------------
  238.  
  239. Node* Node::NextTopDown(ODSiblingOrder siblingOrder)
  240. {
  241.     Node* child;
  242.     if (siblingOrder == kODFrontToBack)
  243.         child = this->GetFirstChild();
  244.     else
  245.         child = this->GetLastChild();
  246.     
  247.     if (child)
  248.         return child;
  249.     else 
  250.     {
  251.         Node* sibling;
  252.         if (siblingOrder == kODFrontToBack)
  253.             sibling = this->GetNextSibling();
  254.         else 
  255.             sibling = this->GetPreviousSibling();
  256.  
  257.         if (sibling) 
  258.             return  sibling;
  259.         else 
  260.             return this->GetNextAunt(siblingOrder);
  261.     }
  262.     return kODNULL;
  263. }
  264.  
  265. //------------------------------------------------------------------------------
  266. // Node::Node
  267. //
  268. // Description
  269. //------------------------------------------------------------------------------
  270.  
  271. Node* Node::GetNextAunt(ODSiblingOrder siblingOrder)
  272. {
  273.     Node* parent = this->GetParent();
  274.     
  275.     if (parent)
  276.     {
  277.         Node* sibling;
  278.         if (siblingOrder == kODFrontToBack)
  279.             sibling = parent->GetNextSibling();
  280.         else
  281.             sibling = parent->GetPreviousSibling();
  282.         
  283.         if (sibling) 
  284.             return sibling;
  285.         else 
  286.             return parent->GetNextAunt(siblingOrder);
  287.     }
  288.     else
  289.         return kODNULL;
  290. }
  291.  
  292. //------------------------------------------------------------------------------
  293. // Node::Node
  294. //
  295. // Description
  296. //------------------------------------------------------------------------------
  297.  
  298. Node* Node::FirstBottomUp(ODSiblingOrder siblingOrder)
  299. {
  300.     Node* child;
  301.     if (siblingOrder == kODFrontToBack)
  302.         child = this->GetFirstChild();
  303.     else
  304.         child = this->GetLastChild();
  305.  
  306.     if (child)
  307.         return child->FirstBottomUp(siblingOrder);
  308.     else
  309.         return this;
  310. }
  311.  
  312. //------------------------------------------------------------------------------
  313. // Node::Node
  314. //
  315. // Description
  316. //------------------------------------------------------------------------------
  317.  
  318. Node* Node::NextBottomUp(ODSiblingOrder siblingOrder)
  319. {
  320.     Node* parent = this->GetParent();
  321.  
  322.     if (parent)
  323.     {
  324.         Node* sibling;
  325.         if (siblingOrder == kODFrontToBack)
  326.             sibling = parent->GetChildAfter(this);
  327.         else
  328.             sibling = parent->GetChildBefore(this);
  329.         
  330.         if (sibling)
  331.             return sibling->FirstBottomUp(siblingOrder);
  332.         else
  333.             return parent;
  334.     }
  335.     else
  336.         return kODNULL;    
  337.  
  338.     return kODNULL;
  339. }
  340.  
  341. //======================================================================================
  342. // NodeTraverser
  343. //======================================================================================
  344.  
  345. //------------------------------------------------------------------------------
  346. // NodeTraverser::NodeTraverser
  347. //
  348. // Description
  349. //------------------------------------------------------------------------------
  350.  
  351. NodeTraverser::NodeTraverser(Node* root, 
  352.                     ODTraversalType traversalType, 
  353.                     ODSiblingOrder siblingOrder)
  354. {
  355.     fRoot = root;
  356.     fCurrent = kODNULL;
  357.     fTraversalType = traversalType;
  358.     fSiblingOrder = siblingOrder;
  359. }
  360.  
  361. //------------------------------------------------------------------------------
  362. // NodeTraverser::NodeTraverser
  363. //
  364. // Description
  365. //------------------------------------------------------------------------------
  366.  
  367. NodeTraverser::~NodeTraverser()
  368. {
  369. }
  370.  
  371. //------------------------------------------------------------------------------
  372. // NodeTraverser::NodeTraverser
  373. //
  374. // Description
  375. //------------------------------------------------------------------------------
  376.  
  377. Node*    NodeTraverser::First()
  378. {
  379.     if (fRoot)
  380.     {
  381.         if (fTraversalType == kODTopDown)
  382.             fCurrent = this->FirstTopDown(fRoot);
  383.         else if (fTraversalType == kODBottomUp)
  384.             fCurrent = this->FirstBottomUp(fRoot,fSiblingOrder);
  385.         else if (fTraversalType == kODChildrenOnly)
  386.         {
  387.             if (fSiblingOrder == kODFrontToBack)
  388.                 fCurrent = fRoot->GetFirstChild();
  389.             else
  390.                 fCurrent = fRoot->GetLastChild();
  391.         }
  392.         return fCurrent;
  393.     }
  394.     else
  395.         return kODNULL;
  396. }
  397.  
  398. //------------------------------------------------------------------------------
  399. // NodeTraverser::Next
  400. //
  401. // Description
  402. //------------------------------------------------------------------------------
  403.  
  404. Node*    NodeTraverser::Next()
  405. {
  406.     if (fCurrent)
  407.     {
  408.         if (fTraversalType == kODTopDown)
  409.             fCurrent = this->NextTopDown(fCurrent, fSiblingOrder);
  410.         else if (fTraversalType == kODBottomUp)
  411.             fCurrent = this->NextBottomUp(fCurrent, fSiblingOrder);
  412.         else if (fTraversalType == kODChildrenOnly)
  413.         {
  414.             if (fSiblingOrder == kODFrontToBack)
  415.                 fCurrent = fCurrent->GetNextSibling();
  416.             else
  417.                 fCurrent = fCurrent->GetPreviousSibling();
  418.         }
  419.         return fCurrent;
  420.     }
  421.     else
  422.         return kODNULL;
  423. }
  424.  
  425. //------------------------------------------------------------------------------
  426. // NodeTraverser::SkipChildren
  427. //
  428. // Description
  429. //------------------------------------------------------------------------------
  430.  
  431. void NodeTraverser::SkipChildren()
  432. {
  433.     Node* next = kODNULL;
  434.     Node* skipTo = kODNULL;
  435.     Node* test = kODNULL;
  436.  
  437.     if (fCurrent)
  438.     {
  439.         if (fTraversalType == kODTopDown)
  440.         {
  441.             if (fSiblingOrder == kODFrontToBack)
  442.                 next = fCurrent->GetNextSibling();
  443.             else
  444.                 next = fCurrent->GetPreviousSibling();
  445.  
  446.             if (!next)
  447.                 next = fCurrent->GetNextAunt(fSiblingOrder);
  448.  
  449.             test = fCurrent;
  450.             while ( test && (test != next) )
  451.             {
  452.                 skipTo = test;
  453.                 test = this->NextTopDown(test, fSiblingOrder);
  454.             }
  455.  
  456.             fCurrent = skipTo;
  457.         }
  458.     }
  459. }
  460.  
  461. //------------------------------------------------------------------------------
  462. // NodeTraverser::IsNotComplete
  463. //
  464. // Description
  465. //------------------------------------------------------------------------------
  466.  
  467. ODBoolean    NodeTraverser::IsNotComplete()
  468. {
  469.     return (fCurrent != kODNULL);
  470. }
  471.  
  472. //------------------------------------------------------------------------------
  473. // NodeTraverser::FirstTopDown
  474. //
  475. // Description
  476. //------------------------------------------------------------------------------
  477.  
  478. Node* NodeTraverser::FirstTopDown(Node* node)
  479. {
  480.     return node;
  481. }
  482.  
  483. //------------------------------------------------------------------------------
  484. // NodeTraverser::NextTopDown
  485. //
  486. // Description
  487. //------------------------------------------------------------------------------
  488.  
  489. Node* NodeTraverser::NextTopDown(Node* node, ODSiblingOrder siblingOrder)
  490. {
  491.     Node* child;
  492.     if (siblingOrder == kODFrontToBack)
  493.         child = node->GetFirstChild();
  494.     else
  495.         child = node->GetLastChild();
  496.     
  497.     if (child)
  498.         return child;
  499.     else if (node != fRoot)
  500.     {
  501.         Node* sibling;
  502.         if (siblingOrder == kODFrontToBack)
  503.             sibling = node->GetNextSibling();
  504.         else 
  505.             sibling = node->GetPreviousSibling();
  506.  
  507.         if (sibling) 
  508.             return  sibling;
  509.         else 
  510.             return this->GetNextAunt(node, siblingOrder);
  511.     }
  512.     return kODNULL;
  513. }
  514.  
  515. //------------------------------------------------------------------------------
  516. // NodeTraverser::GetNextAunt
  517. //
  518. // Description
  519. //------------------------------------------------------------------------------
  520.  
  521. Node* NodeTraverser::GetNextAunt(Node* node, ODSiblingOrder siblingOrder)
  522. {
  523.     Node* parent = node->GetParent();
  524.     
  525.     if (parent && (parent != fRoot))
  526.     {
  527.         Node* sibling;
  528.         if (siblingOrder == kODFrontToBack)
  529.             sibling = parent->GetNextSibling();
  530.         else
  531.             sibling = parent->GetPreviousSibling();
  532.         
  533.         if (sibling) 
  534.             return sibling;
  535.         else 
  536.             return this->GetNextAunt(parent, siblingOrder);
  537.     }
  538.     else
  539.         return kODNULL;
  540. }
  541.  
  542. //------------------------------------------------------------------------------
  543. // NodeTraverser::FirstBottomUp
  544. //
  545. // Description
  546. //------------------------------------------------------------------------------
  547.  
  548. Node* NodeTraverser::FirstBottomUp(Node* node, ODSiblingOrder siblingOrder)
  549. {
  550.     Node* child;
  551.     if (siblingOrder == kODFrontToBack)
  552.         child = node->GetFirstChild();
  553.     else
  554.         child = node->GetLastChild();
  555.  
  556.     if (child)
  557.         return this->FirstBottomUp(child, siblingOrder);
  558.     else
  559.         return node;
  560. }
  561.  
  562. //------------------------------------------------------------------------------
  563. // Node::Node
  564. //
  565. // Description
  566. //------------------------------------------------------------------------------
  567.  
  568. Node* NodeTraverser::NextBottomUp(Node* node, ODSiblingOrder siblingOrder)
  569. {
  570.     if (node == fRoot)
  571.         return kODNULL;
  572.         
  573.     Node* parent = node->GetParent();
  574.  
  575.     if (parent)
  576.     {
  577.         Node* sibling;
  578.         if (siblingOrder == kODFrontToBack)
  579.             sibling = parent->GetChildAfter(node);
  580.         else
  581.             sibling = parent->GetChildBefore(node);
  582.         
  583.         if (sibling)
  584.             return this->FirstBottomUp(sibling, siblingOrder);
  585.         else
  586.             return parent;
  587.     }
  588.     else
  589.         return kODNULL;    
  590.  
  591.     return kODNULL;
  592. }
  593.  
  594.